A typical communications network includes many hosts interconnected by various data communication devices. The data communications devices can be routers, bridges, switches, network access servers, gateways, hubs, concentrators, repeaters and so forth which can exchange data over an interconnection of data links. The data links may be physical connections or may be provided using wireless communication mechanisms. Applications which execute on the hosts can use various protocols to transfer data such as voice, video and computer application data (all collectively referred to herein as xe2x80x9cdataxe2x80x9d) across the network. The hosts may be general purpose computer systems such as personal computers, workstations, minicomputers, mainframes and the like, or the hosts may be dedicated special purpose computer systems or devices such as web-site kiosks, voice/data terminals, telephony, facsimile or email servers, video servers, audio servers, and so forth. Each host (computer system or other networked device) couples either physically or via a wireless data link to one or more of the data communications devices that form the network.
Generally, there are two basic implementations of modern communications network architectures: connection-based network architectures (FIG. 1) and connectionless network architectures (FIG. 2).
Connection-based Networks
FIG. 1 illustrates an example of a prior art connection-based network 100. Generally, the connection-based network 100 provides a single dedicated data path or xe2x80x9cconnectionxe2x80x9d 103 through each data communications device 120 through 127 for all data (not specifically shown) transferred, for example, between hosts 118 and 119. The dedicated connection path 103 represents the resources (e.g. circuits, buffers, ports, bandwidth, etc.) in each data communications device (120, 124, 125, 126 and 127) that are pre-allocated or dedicated to handle data transmission for the duration of the data communication session between the hosts 118, 119. Each data communications device 120 through 127 on the dedicated connection path 103 maintains the connection 103 (i.e., keeps resources allocated) for the life of the data communications session, even though data flow may not be constant (e.g. the data flow may be bursty) at all times during the session.
Once a connection is established in each of the data communications devices 120, 124, 125, 126 and 127 (defining the connection path 103), subsequent data transmissions between the hosts 118 and 119 may be performed with little additional work. This is because there is no need for each data communications device to determine a complex routing decision (i.e., selecting from multiple paths) for each data portion (e.g., packet, frame or cell) that arrives at the device. Rather, as a data portion arrives at one of the devices 120 through 127, the device simply channels the data along the pre-established connection 103 that is assigned for that data. Data communications devices used in connection-based network architectures are typically referred to as xe2x80x9cswitching devicesxe2x80x9d or xe2x80x9cswitches.xe2x80x9d
An example of a well known connection-based network is the Public Switched Telephone Network (PSTN). In a typical telephone network, when a caller picks up a telephone handset and dials a telephone number, one or more switches in the telephone network configure resources (e.g. phone lines and electronic switch circuitry) to provide a dedicated connection between the source (caller) and destination (callee) telephones. The connection exists for the duration of the telephone call and is maintained whether or not people are actually speaking to each other. All voice information takes the same connection path through the telephone network from one telephone to another. The connection is terminated (i.e., torn-down) when either party hangs-up their handset, causing each telephone switch used along the connection path to release any resources used for that connection.
In the context of computer networks, an example of a connection-based network is a network constructed from an interconnection of Asynchronous Transfer Mode (ATM) switches. ATM switches allow connections (typically called circuits or virtual circuit connections) to be established between hosts (which are typically computer systems). ATM switches transmit data in relatively small portions called cells using virtual circuits within each ATM switch that are dedicated to transferring data for the life of a particular session of data communications.
Changing the path of data for an active data communications session in a connection-based network is difficult since, generally, all data communications devices (e.g., ATM switches, telephone switches) on the entire connection path must reconfigure new connection information for the data and furthermore, these changes must be coordinated precisely across all the data communications devices. As such, connection-based network devices such as ATM switches generally provide only a single but very reliable path (e.g., connection 103 in FIG. 1) through the network upon which the data travels from one host to another during a session of data communication.
Connectionless Networks
FIG. 2 illustrates an example of a connectionless network 101. In contrast to connection-based network architectures, connectionless network architectures such as connectionless network 101 generally operate using a hop-by-hop methodology to transfer data within the network. During a single session of data communications, various data portions for that session, such as packets, may each take different paths 104 through the network 101, hence the name connectionless network. As an example, for data sent from host 105 to host 106, the data communication device 110 may forward some data to data communications device 111, while other data may be sent to data communications device 114, depending upon current conditions in the network 101. Conditions such as congestion or data link and/or data communications device failures may change during the life of a single data communications session and may affect decisions on where to send or route data with the connectionless network.
As indicated above, the process of determining the route(s) on which data shall be transferred to a network is usually called routing. There are various types of routing operations commonly used in communications networking. Three of such routing operations, referred to as routing protocols, are: unipath routing, equal cost multipath routing, and unipath multipath routing. The routing protocols enable a device to select a particular path of link for data transfers. Once selected, a process of forwarding is used to transfer data from device to device in the network. Both routing and forwarding occur in both connectionless and connection-oriented networks. However, a device in a connectionless network which routes and forwards data is referred to loosely as a xe2x80x9crouter.xe2x80x9d
In general, unipath routing protocols use only one path at a time to a given destination, even if several equally good paths are available. Most routing protocols are unipath, or have a unipath mode of operation. A commonly used routing protocol called Open Shortest Path First (OSPF) typically operates in a unipath mode unless equal-cost multipath routing is enabled or turned on in the protocol.
Equal-cost multipath routing protocols will distribute data traffic such as packets across multiple paths to a given destination, but only if there are multiple paths available, each with the same minimum cost or weight. Costs and weights are simply metrics associated with paths that can be used to determine path selection if multiple paths are available to reach a single destination. In equal cost multipath routing, if there is only one path available with the minimum cost, then the equal-cost multipath routing protocol will choose only that one path.
Unequal-cost multipath routing protocols may distribute traffic across multiple paths to a given destination, even where some of the paths have greater cost than others. Unequal-cost multipath modifications to OSPF have been proposed.
As noted above, a router is one type of data communications device commonly used to transfer portions of data, such as packets, in a connectionless network using one of the above mentioned routing protocols. Generally, a router analyzes addressing or other information in each packet received on a port (i.e., from a data link) to determine which path 104 (i.e., which port) to forward the packet to next within the network 101. A routing protocol such as OSPF can be used to establish and maintain routing tables (not shown in FIG. 2) indicating the current available paths for data based on a destination address of the data. The routing tables may dynamically change in response to the routing protocol detecting changing network conditions. Changes to the routing tables can occur at any time and can cause packets in a stream of data bound for the same destination (i.e., a host) to be directed onto different data links.
Connectionless networks have proven to be quite reliable due to their ability to make real-time routing decisions as data is transferred during a data communications session. The reconfiguration of routing tables and redirection of data in a connectionless network can occur in a relatively short time after the routing protocol learns of a problem (e.g. congestion or device failure) within the network. Generally, routing decisions made by a protocol such as OSPF are affected primarily by the state of the connectionless network, and not by the requirements of the individual connections themselves, unlike connection-based network devices (e.g., switches) which, by contrast, establish connections once based on where the data is to arrive and then maintain the connections (e.g., path 103 in FIG. 1) for the duration of a data communications session. Accordingly, re-routing in a connectionless network is a fast and relatively simple operation. An example of a connectionless network is a computer network operating the Internet Protocol (IP) (often referred to as an IP network), such as the Internet.
Switch Redundancy
Though switches used in connection-based networks offer high speed data transfer capabilities, they have limited or no ability to re-route data traffic in the event of network failures. As such, switches are often designed with high levels of redundancy to allow continued operation in the event of failure(s). Many components in a data communications switch have a secondary (i.e., spare or redundant) component designed to be used in the event of a failure of the first component. For example, a highly redundant switch may have redundant line cards, power supplies, fans, backplanes, switch fabrics (circuitry interconnecting the various line cards and data ports in the switch), and control cards. Switches using redundant components must also include redundant circuitry and/or redundant control software to handle the changeover required from a primary component to the redundant component in the event of a failure.
In redundant switch designs, a redundant component typically exists in a warm- or hot-standby relationship to the primary component (i.e., active) counterpart. For example, in the case of redundant line cards, connection state information may be concurrently programmed in both an active (e.g. primary) and a hot-standby (i.e., redundant or secondary) line card. The active line card uses the connection state information to perform data transfers, while the hot-standby line card performs no data transfers. However, in the event of a failure of the active line card, the hot-standby line card can take over and maintain the existing connections to ensure minimal circuit disruption. In warm-standby redundancy, when a changeover is required from an active line card that fails to the warm-standby line card, the warm-standby line card is typically unable to maintain the connection and thus resets the connections and proceeds to re-establish them.
Active (i.e. primary) and standby (hot or warm) switch components and processes are coupled in a relationship in that they are two components (or processes) to do the same job or task at different times, and thus they do not act independently and/or concurrently to each other. The coupling relationship exists so that when the active component fails, the standby component can take over the same job. Switch redundancy reduces the need to re-route connections. However, if re-routing connections in a connection-based (i.e., switched) network is supported and must be performed (e.g., in event of total failure of required switch components), the process may take several minutes to re-establish all connections through a different switch path. Typical connection re-routing times required for connection-based networks are often too long for situations requiring high reliability.
Routable Switches
Relatively recent advancements in connection-based networking technology, particularly in networks that use ATM or Frame-Relay switches, have provided mechanisms which allow a connection-based switch to act more like a connectionless router. One such technology is known as xe2x80x9ctagxe2x80x9d or xe2x80x9clabelxe2x80x9d switching or xe2x80x9cMultiple Protocol Label Switchingxe2x80x9d (MPLS). MPLS uses a label distribution protocol such as the xe2x80x9cLabel Distribution Protocolxe2x80x9d (LDP), the xe2x80x9cConstraint Based Routing with LDPxe2x80x9d (CR-LDP) protocol, the xe2x80x9cResource Reservation Protocolxe2x80x9d (RSVP) or a similar protocol to allow a switch to be controlled in conjunction with a routing protocol such as OSPF, BGP, IS-IS or similar routing protocol. The LDP protocol will be used as an example label distribution protocol herein when discussing the operation of MPLS technology. Generally, in MPLS technology, LDP and the routing protocol work together to configure virtual circuits (VCs) within a prior art connection-based switch. The VCs are optimized for the needs of connectionless traffic.
FIG. 3 illustrates a conventional switch network 152 in which a number of connection-based data switches 170 through 173 are configured to operate much like connectionless routers. As shown in FIG. 3, network devices called Label Switch Routers (LSRs) 160 through 163 are formed from the prior art data switches 170 through 173, which may be ATM switches for example, that are each configured to operate in conjunction with a respective prior art route controller 175 through 178. The LSRs 160 through 163 operate in conjunction with the label edge routers 153, and 154 on the connectionless networks 150 and 151 to provide connectionless data transfer capability through the switch network 152.
Within each prior art LSR 160 through 163, the prior art route controllers 175 through 178 operate LDP and a routing protocol (not specifically shown) in communication with the label edge routers 153 and 154 to implement the label switching technology. As such, the LSRs 160 through 163 (each formed from a switch coupled with a route controller) provide a route or data path 141 (i.e., many of which form a network 141) that provide connectionless data transfer capabilities within the switch network 152.
Details of the operation of prior art label switching technology, prior art route controller operation, and the relationship of these technologies to prior art data switches can be found in the documents listed in Appendix A, located at the end of the detailed description section of the invention. The entire contents of each of the documents in Appendix A is hereby incorporated by reference in their entirety. MPLS technology and it""s use of label distribution protocols such as LDP and routing protocols are also discussed in these documents. A brief overview of this technology follows.
Generally, as illustrated in switch network 152, the coupling of each route controller 175 through 178 to a respective data switch 170 through 173 forms respective Label Switch Routers (LSRs) 160 through 163 (labeled LSR1 through LSR4). Essentially, each LSR 160 through 163 provides many of the capabilities of a connectionless router due to the route controllers (175 through 178) implementation of LDP and a routing protocol in conjunction with the data transfer capabilities provided by each data switch 170 through 173. As discussed in detail in the aforementioned documents (Appendix A), in MPLS, the LDP protocol works with a routing protocol such as OSPF to allow the route controllers 175 through 178 to dynamically control the respective data switches 170 through 173 to establish and route data over connections 141 to one or more other LSR""s 160 through 163. In this manner, the LSRs 160 through 163 provide multiple data paths 141 (e.g. routes) through the switch network 152, which provides the data transfer capability that is typical of a connectionless network architecture. This contrasts sharply with the single data path 103 (FIG. 1) provided for a session of data communication in the network 100 of connection-based switches 120 through 127, as discussed above.
FIG. 4 illustrates data flow through a single prior art LSR, which may be any one of the LSRs 160 through 163 in FIG. 3. Since the LSRs 160 through 163 each operate much like a conventional connectionless router, a single network of routes 141 is provided between each LSR 160 through 163 within the switch network 152. The data network 141 may support connectionless data transfer and may operate as an Internet Protocol (IP) network, for example. In such a case, packets for a connectionless session of IP data between connectionless networks 150 and 151 (FIG. 3) may be transferred through the switch network 152 using the IP data paths 141 between the LSRs 160 through 163, and each packet may potentially take a different route. For example, LSR1160 may send IP packets to either LSR2161 or LSR3162. If the switch network 152 is an ATM switch network, the IP packets are each broken into a number of commonly labeled ATM cells for the actual data transfer operation.
Label Switching
FIGS. 5A, 5B and 5C provide a more detailed illustration of the operational architecture of a prior art Label Switch Router (LSR) 160 and its relationship to a prior art Label Edge Router (LER) 153 and another LSR (e.g., LSR2161) when performing label switching. As illustrated in FIG. 5A, the data switch 170 (which is an ATM switch in this example) maintains a label virtual circuit (LVC) 145 between itself and the label edge router 153 and the LSR2161 (i.e., the data switch 171 in LSR2161 in FIG. 3). The LVC 145 is essentially a switched network connection that gets instantiated and controlled under direction from the route controller 175 in LSR 160, according to the needs of the routing protocol (e.g. OSPF). The LVC 145 provides a route for data transfer on the IP network 141 (using switched virtual circuit connections to transfer data) between each LSR 160 through 163.
The switch control interface 180 allows a separate control plane operating separate processing logic (which in this example is the route controller 175 operating the label switching protocols) to control and manipulate switch resources (e.g., circuits, buffers, queues, interfaces, ports, etc.) in the data switch 170 to provide LVCs 145, as needed. Generally, to do so, an MPLS process 182 in each route controller 175 through 178 executes a label exchange protocol (e.g., LDP) and a routing protocol (e.g. OSPF) and uses the switch control interface 180 to setup, remove or change the LVCs 145 in each LSR 160 through 163 according to the needs of routes. Application or session data (i.e., IP packets travelling from LER 153 to LER 154) passes only through the data switch 170 via the LVCs 145 and does not get passed up to the route controllers 175 through 178. However, each route controller 175 through 178 does maintain its own IP network address, and thus the LDP and routing protocol and control information (e.g., protocol packets) 174 can be directed (i.e., routed) to specific route controllers 175 through 178 using the LVCs 145 as well. This allows each route controller 175 through 178 to be an independently IP addressable network entity, and thus the combination of the router controllers 175 through 178 and the data switches 170 through 173 form respective individual LSRs 160 through 163 that provide routing capability in the switch network 152 (FIG. 3).
While not shown in detail, each Label Edge Router LER 153 and 164 (FIG. 3) serves as an end point for the label virtual circuits 145 and can communicate with the MPLS processes (e.g., LDP and OSPF) 182 in the route controllers 175 through 178 to create the connectionless network connections (i.e., routes) between the LSRs 160 through 163 via the label virtual circuits 145. The operation of label switching will be further understood with reference to FIGS. 5B and 5C.
FIG. 5B illustrates a prior art IP address/label lookup table 185 maintained, for example, by the Label Edge Routers 153 and 154 and by each MPLS control processes 182 in the LSRs 160 through 163. During the label switching operation, when a particular IP packet (not shown) is to be transferred, for example, from the connectionless network 150 (FIG. 3) across the switch network 152 to the connectionless network 151, the Label Edge Router 153 examines the destination IP address of the packet. If the IP address exists in column 185-1 in FIG. 5B, then the packet is transmitted as a series of commonly labeled ATM cells (not shown) out of the port (in the LER 153, not specifically shown) indicated by the label in the label/interface table 190 in FIG. 5C. In this case, packets destined for an IP address of any host on connectionless network 151 (or for the IP address of any route controller 175 through 178 in network 152) are sent as a series of commonly labeled ATM cells to the LSR1160. Each labeled ATM cell includes label information corresponding to the IP address of the packet shown in column 185-2 of table 185 (e.g., ATM cells are labeled 1/1 for a packet having an IP address equal to 1.2.3.4). If no label entry exists for the IP address in table 185, then the LER 153 creates a new IP address/label entry (i.e., new row entry in table 185) for the destination IP address.
As explained in more detail in the MPLS documentation incorporated by reference (Appendix A) above, the MPLS processes 182 (FIG. 5A) in each route controller 175 through 178 also maintain an IP address/label table (e.g. 185) and a label/interface table (e.g., 190) which are similar to those shown in FIGS. 5B and 5C. As such, each is able to detect incoming/arriving labeled cells and can match the labels of those cells via column 190-1 (Table 190 in FIG. 5B) to determine the proper outgoing port (e.g., an ATM port in the data switch) as specified in column 190-2 (FIG. 5C). Using the OSPF or a similar routing protocol, the MPLS process 182 can also determine new routes for packets as needed. The label/interface table 190 (FIG. 5C) and/or the IP address/label table 185 (FIG. 5B) can be dynamically modified and updated accordingly to provide route changes for labeled ATM cells. By altering the tables 185 and 190, re-routing of data can be accomplished in the IP network 141. Generally, since ATM cells do not have associated IP addresses of their own, each cell is provided with a corresponding label that is associated with the IP address of the data (i.e., packet) which the ATM switch 170 is transporting. In an ATM network, the label information is carried in the virtual connection identifier field in the cell. Thus, on each ATM link (i.e., each physical connection), a label corresponds to the different virtual circuit. All cells used to transport data for a particular packet will share a common label and will be routed in a similar manner. The LSRs 160 through 163 therefore benefit from the high speed throughput of the data switches 170 through 173 as well as the flexibility of altering data paths provided by label switching and routing techniques.
Multipath Routing
The prior art MPLS processes 182 in each LSR 160 through 163 can execute any type of routing protocol, such as OSPF. As noted above, the OSPF protocol supports a type of connectionless multipath routing. Using multipath routing, a data communications device such as a router or LSR (e.g., 160 through 163 in FIG. 3) may use different segments of the same IP network (e.g., different paths or routes in IP network 141) to forward packets towards any specific final destination. By way of example, in FIG. 3, the network 141 formed from the LSRs 160 through 162 provides a variety of paths or routes that data may take to successfully reach a destination. To transmit a packet (as a series of ATM cells) from LSR1160 to LSR4163, a route may be taken straight from LSR1160 to LSR4164, or data may be routed to either LSR2161 or to LSR3162, and then on to LSR 163. Using multi path routing, each of these different data routes may be assigned a weight or cost metric. A data route with a lessor weight or cost may be favored (i.e., may receive more data) over a data route having a higher weight. Thus, if two routes to LSR 163 (e.g., the path between LSR1160 and LSR2161 and the path between LSR1160 and LSR3162) are given the same cost, then data is sent more or less equally across the two routes. For example, one packet may be sent from LSR1160 to LSR2161 while another packet bound for the same eventual destination may be sent from LSR1160 to LSR3163. This is a description of equal cost multipath routing which allows data to be distributed over multiple equally weighted routes. Unipath multipath routing, also as indicated above, can be used to select a route having the lowest cost for data transfers. If many routes all have the different cost, unipath routing selects may select one or more of the routes for data transfer. In any event, multiple paths can be used.
Certain drawbacks exist in prior art implementations of connection-based switched networks that incorporate routing techniques, such as switched networks that use label switching as explained in the above examples. On such drawback is the requirement that connection-based switched networks be highly redundant. As noted above, data switches (e.g., 170 through 173 in FIGS. 3, 4 and 5A) operating alone (i.e., without a route controller) have a very limited ability to reroute data and are therefore quite redundant in design. The redundant componentry in a data switch allows certain failures to occur without severely disrupting the transport of data through the switch.
When a data switch (e.g., one of 170 through 173) is combined with a route controller (e.g., one of 170 through 175) to form an LSR (e.g., 160 through 163), the capability to re-route data over a switched network further enhances network reliability, as failed LSR""s may be avoided (routed around) via re-routing. However, from the perspective of a single LSR (i.e., just one of 160 through 163), the highly redundant architecture of the data switch portion 170 through 173 does not necessarily extend, nor scale well, to the route controller portion 175 through 178. That is, redundant implementations of route controllers (e.g., redundant ones of route controllers 175 through 178 for a single data switch) in a prior art LSR do not exist due to difficulty in maintaining consistency of information, such as routing table and connection state information, between a primary route controller that suddenly fails and a hot or warm standby route controller that must take over for the failed primary route controller.
The present invention is based in part on the observation of such drawbacks and provides an alternative to systems that attempt to use hot or warm standby route controllers used within an LSR. Generally, the present invention provides duplicate route controllers which each operate independently and concurrently to provide route controller redundancy within an LSR. This design differs significantly from hot or warm standby switch designs in which a standby component takes over for a primary component in the event of a failure. Instead, the techniques and architectures provided by this invention allow multiple route controllers, called label switch controllers (LSCs), to concurrently control partitions of resources within the same data switch at the same time. Within a single LSR, there need not be any relationship between the two (or more) redundant LSCs, nor need there be knowledge or sharing of each others existence, state, connections or operation information once configured. Each LSC controls a partition of the switch resources to support a unique, but parallel route, in relation to the other LSCs coupled to the same switch.
As a result of such a design, during operation of one embodiment which uses multipath routing protocol, the architecture of the invention can provide multiple parallel IP networks which may be in full or in part physically and/or logically parallel. As will be explained in more detail, multipath routing techniques allow data to be transferred concurrently using each of the parallel IP networks (i.e., each of the parallel routes) provided by the separate and concurrently operating LSCs. In the event of a failure of one of the networks (e.g., a failure of one of the multiple LSCs in an LSR), the other IP network(s) supported by the other still functioning route controller(s) can share the data load formerly carried by the failed IP network, as each network has a route having equal costs.
In another embodiment which uses unipath routing, multiple LSCs can be similarly configured with parallel routes to control a single switch. A label edge router (at the edge of the switch network) can use unipath routing techniques to select one of the parallel routes supported by one of the similarly configured LSCs. The LSC supporting the selected route can provide the required data transfer capabilities through the switch and can use the bulk of the data switches resources (i.e., bandwidth, buffers, memory, etc.), while switch resources required for the other redundant LSCs remain minimally allocated. In the event of a failure of the LSC supporting the selected route, a route of another similarly configured LSCs coupled to the same switch can be selected by the LER. Switch resources used by virtual circuits established for the route of the failed LSC are released and can then be used by virtual circuits established to support the newly selected route(s) supported by the other LSC. Since the other LSC is already configured with the same routes as the failed LSC, there is no need for the failed LSC to provide state information to the second LSC that takes over. Both the multipath and unipath routing implementations have no limit to how many LSCs may be coupled to a single data switch, and thus redundancy may be greater than two-fold.
More specifically, the present invention provides a data communications device which includes a data switch mechanism. The data switch mechanism includes i) at least one port for receiving data; ii) at least one port for transmitting data; and iii) data switch resources coupled to the port (s) for receiving data and to the port(s) for transmitting data. The data switch resources are divided or distributed into a plurality of partitions. Each partition provides resources for concurrently and independently supporting at least one respective data route between the port(s) for receiving data and the port(s) for transmitting data. Each of the plurality of partitions including an interface allowing that partition to be concurrently and independently controlled by a respective switch control mechanism. This embodiment of the invention thus provides a data switching mechanism, such as an ATM, Frame-Relay or other connection-based switch to have interfaces for multiple switch controllers. Each partition supports a route through the switch. Preferably, the different routes are parallel in nature. Prior art switches generally lack the ability to interface to more than one of the same type of switch control mechanism and thus do not provide multiple partitions that can have the same routes. Such redundancy enables the invention to support highly reliable networking applications, as will be explained more fully below.
Another arrangement of the invention includes a plurality of switch control mechanisms coupled to the data switching mechanism described above. Each of the switch control mechanisms couples to the data switching mechanism via a respective interface of a partition and each concurrently and independently operates according to at least one connection routing protocol to advertise a respective route for data through the respective partition of the data switch resources. Since each switch control mechanism operates independently and concurrently of the others, multiple routes that are parallel can be provided by a data communications device configured as such.
In another configuration, the partitions of the data switch resources include a first partition and a second partition and the switch control mechanisms include a first and second switch control mechanism. In this arrangement, the first switch control mechanism controls data switch resources in the first partition according to a first connection routing protocol to provide a first route for data through the first partition, while the second switch control mechanism controls data switch resources in the second partition according to a second connection routing protocol to provide a second route for data through the second partition. In this manner, each switch control mechanism operates independently of the others. This allows failure of one to have little effect on the operation of the others.
In another arrangement, the first and second connection routing protocols are configured in parallel to offer the same routes, such that the first and second routes provided through the first and second partitions are parallel routes. This allows data to be routed via both routes to the same destination at the same time, or at different times in which case the first route can be used first, and if this route fails, the second route can be used.
Generally, in another configuration, the first route provided within the first partition is established as a corresponding first switched connection and the second route provided within the second partition is established as a corresponding second switched connection. The first and second switched connections handle data transfers concurrently according to a multipath routing protocol that distributes data between the first and second routes, such that the first and second switch control mechanisms support routes for distinct parallel networks that operate to transfer data concurrently through the data communications device. Since multipath routing is used and there are a plurality of parallel routes, each supported by a distinct respective switch control mechanism, concurrently operating parallel networks are provided through a single data communications device. Such networks provide significant advantages concerning the quality of service or redundancy in the event of failures.
As such, in another arrangement, a means is provided for detecting an inability of the first switch control mechanism to support the first route within the first partition. This may done, for instance, using the existence of not of communication between the switch control mechanism and a slave process in its respective partition, or the routing protocol may provide such fault detection. Also provided is a means, in response to the means for detecting, for re-routing a data stream transferred using the first route within the first partition to the second route within the second partition.
Another arrangement provide the above means in conjunction with a means for de-allocating data switch resources from the first partition used to support the first connection, and a means for removing the first connection from the first partition. A data switch resource management process can be used for this purpose, as will be explained in more detail later. Also included in this arrangement is a means, in response for the means for de-allocating, for allocating at least a portion of the data switch resources de-allocated from the first partition to the second partition, such that the portion of data switch resources that are de-allocated from the first partition are allocated to the second, partition in order to support data transfers on the second route provided by the second connection. In this manner, when a switch control mechanism fails, resources are released for use by other connections that now will handle the data transfers formerly handled by the failed routes.
In another configuration, the first route provided within the first partition is established as a corresponding first switched connection and the second route provided within the second partition has no corresponding second switched connection in the second partition. This configuration thus only use one route at a time (having a corresponding connection) to perform data transfers. The first switched connection handles data transfers according to a unipath routing protocol that initially selects the first route to perform data transfers. In this configuration then, the first and second switch control mechanisms each support routes for distinct parallel networks, but only one of such routes is selected according to the unipath routing protocol to initially transfer data through the data communications device.
In yet another arrangement, a means is provided for detecting an inability of the first switch control mechanism to support the first route within the first partition. For instance, a failure of an LSC can be detected. Also provided, in response to the means for detecting, is a means to establish a second connection in the second partition according to the second route supported by the second switch control mechanism. The second connection is used to provide data transfers of a stream of data formerly transferred through the first connection. This allows one route to handle data after the first route fails.
Related to the above arrangement, another arrangement is provided which includes a means for de-allocating data switch resources from the first partition used to support the first connection, and means for removing the first connection from the first partition. In response for the means for de-allocating, a means is provided for allocating the data switch resources de-allocated from the first partition to the second partition, such that the data switch resources that are de-allocated from the first partition are allocated to the second partition in order to support data transfers on the second route provided by the second connection. In this fashion, one route can be used first, and if it fails, another route can be selected and a connection can be established for the newly selected route. This arrangement uses unipath routing to select individual routes, and work well with a fully-meshed embodiment as will be explained.
In a fully-meshed arrangement there are a plurality of ports on the data communications device, and each port may serve as both an input and an output port. In this case, each of the plurality of partitions has access to a portion of an amount of bandwidth on each of the plurality of ports, such that the at least one respective data connection supported by each partition shares a total amount of bandwidth available on at least one port of the plurality of ports. In other words, the fully-meshed configuration allows the parallel networks to share the same physical links.
In a fully-parallel arrangement, each port may also serve as both an input and an output port, but each of the plurality of partitions has access to a total amount of bandwidth on a respective and exclusive set of ports selected from the plurality of ports, such that data connections maintained within each partition are transferred using the ports assigned to that partition and no others. In this manner, the parallel arrangement allows each network to perform data transfers using physically separate ports, and thus the networks are completely separated.
In another configuration, the data switching mechanism includes a plurality of slave processes. Each slave process is responsible for controlling resources associated with at least one respective port of the data communications device. Each slave process also communicates with at least two of the plurality of switch control mechanisms to receive routing information concerning a route concurrently supported by each of the switch control mechanisms with which the slave process communicates. This allows a port controlled by a slave to support at least two routes from two different switch control mechanisms.
The invention also provides a data communications device comprising a plurality of switch control mechanisms, each operating a respective connection routing protocol. A data switching mechanism is provided in this arrangement and has a coupling to each of the switch control mechanisms. Each of the switch control mechanisms independently and concurrently supports a route through the data switching mechanism according to the respective connection routing protocol operated by the switch control mechanism using resources from an partition of resources assigned to that switch control mechanism.
In one variation of this arrangement, the respective connection routing protocols operating on at least two of the switch control mechanisms are the same connection routing protocols and are configured to support routes that are the same. In this case, the parallel network routes are provided for selection through the data communications device by each of the switch control mechanisms that operate the same connection routing protocol, respectively. The data switching mechanism may be an ATM switch, for example, and the switch control mechanisms may be label switch controllers that operate at least one Internet Routing Protocol and at least one label distribution protocol according to multi-protocol label switching technology in order to concurrently route at least two streams of labeled ATM cells passing through the ATM switch at the same time. This allows ATM networks to have redundant LSCs on each ATM switch as explained herein.
In operation, if one of the switch control mechanisms fails to operate correctly, data transferred using the route supported by the switch control mechanism that fails is subsequently transferred through the data communications device using the route supported by at least one other correctly operating switch control mechanism within the plurality of switch control mechanisms.
Also, in another configuration, each route supported by each switch control mechanism has an associated connection established in the partition supporting that route. The connections associated with all of the routes concurrently operate according to a multipath routing protocol to transfer data through the data communications device in a parallel manner across multiple routes. As such, when one route fails, the connections for remaining non-failed routes continue to operate to transfer data through the data communications device.
As an alternative, one route supported by one of the switch control mechanism has an associated connection established in the partition supporting that route. In this case, the associated connection operates to transfer data through the data communications device according to a unipath routing protocol. When the route of the associated connection fails, a connection for a remaining non-failed route is established and operates to transfer data through the data communications device.
The invention also provides for an Asynchronous Transfer Mode (ATM) switch that includes a data switching mechanism for supporting data connections through the Asynchronous Transfer Mode switch. A plurality of switch control mechanisms are provided, each operating a similarly configured connection routing protocol and each implementing multi-protocol label switching technology to allow routing of labeled ATM cells. Each also independently and concurrently controls a respective partition of resources within the data switching mechanism to control a respective route for data through the Asynchronous Transfer Mode switch. The route controlled by one of the switch control mechanisms is configured in a parallel manner to the route controlled by another of the switch control mechanisms, thus providing a plurality of parallel network routes through the Asynchronous Transfer Mode switch.
An arrangement of such an ATM switch can also include a means for detecting a fault condition within at least one of the switch control mechanisms in the Asynchronous Transfer Mode switch. Also included is a means, responsive to the means for detecting, for re-routing data formerly transferred on a connection associated with a route provided by the at least one of the plurality of switch control mechanisms containing the detected fault condition by using a connection associated with a route provided by another of the at least one of the plurality of switch control mechanisms that does not contain a fault condition. This arrangement allows data streams using one or more connections supported by routes of failed LSC to be re-routed using the existing parallel routes provided by non-failed LSCs. Since the other parallel routes exist, and may already have associated connections, the re-route operation simply selects or uses these other routes.
Also included as an addition to this arrangement is a means, responsive to the means for detecting, for releasing resources controlled by the switch control mechanism that faulted, as well as a means, responsive to the means for releasing, for allowing another one of the switch control mechanisms to obtain control of the released resources. In this manner, data formerly transferred using the route maintained by the switch control mechanism that faulted is now transferred by the another route controlled by one of the switch control mechanisms that obtains control of the released resources.
The invention also provides various unique techniques, such as a method for transferring data through a data communications device. This technique involves configuring a plurality of parallel routes through a switched network device, with each route supported by a respective switch control mechanism interfaced to the data communications device. Each respective switch control mechanism is of the same type and is configured with the same connection routing protocol. The technique then transfers portions of data that are bound for the same destination through the data communications device by selecting, according to a routing protocol, at least one of the routes supported by at least one of the switch control mechanisms and transmits portions of data using a connection established for the selected route. Since multiple routes are offered, and one or more can be selected for use, the technique provides for high levels of redundancy.
The operation of configuring a plurality of parallel routes through the data communications device can further include the operations of analyzing the data communications device to determine a set of available parallel routes provided by each of the respective switch control mechanisms. For example, routing information maintained within the data communications device can be analyzed. The technique can then configure at least one network through the data communications device by selecting at least one route supported by a switch control mechanism within the data communications device for data transfers. Connections are then established within the data communications device according to the selected at least one route.
Techniques of the invention can also detect a failure of one of the routes supported by a switch control mechanism that is used to perform data transfers through the data communications device. In such a case, the technique then re-analyzes the network to determine a new set of available parallel routes provided by at least one switch control mechanism that is operating properly. As an example, the OSPF routing protocol can be used to routinely analyze the network (interconnected devices configured according to the invention) as a matter of course in order to determine available routes. Then, the technique can transfer a plurality of portions of data that are bound for the same destination through the data communications device by selecting, according to the routing protocol, at least one route from the new set of available parallel routes. In this manner, data transfers can still occur even if one route fails.
The routing protocol can be a multipath routing protocol and the route initially selected for the transmission of data cab actually be a plurality of parallel routes, each supported by a respective switch control mechanism. According to this technique, the route selected from the new set of available routes is the set of lowest cost routes supported by properly operating switch control mechanism and excludes the route containing the detected failure. Thus the failed route is avoided while the other parallel routes can still be used.
Alternatively, the routing protocol can be a unipath routing protocol and the route initially selected for the transmission of data is a single route of the plurality of parallel routes. In such a case, the route selected from the new set of available routes is another route supported by another properly operating switch control mechanism that is different from the route containing the detected failure. Thus the unipath technique uses one route, detects a failure, and then uses another route that is concurrently offered in parallel to the first route. Since both routes exist concurrently, each supported by a respective LSC, there is no need for an LSC supporting a newly selected route to obtain connection or state information from the failed LSC. In other words, the second step of transferring is performed without having to transfer state information from a failed switch control mechanism to the one or more switch control mechanism supporting the at least one newly selected route.
Another technique provided by the invention includes a method of transferring data through a data communications device. Generally, the technique configures partitions of resources of a data switching mechanism equally and respectively among a plurality of switch control mechanisms. Each switch control mechanism is then configured to independently and concurrently operate a connection routing protocol. The technique then transfers data through the data communications device by having each switch control mechanism support a route according to operation of a respective connection routing protocol. The routes cause a connection to be formed in the partition of resources configured for that respective switch control mechanism. In this technique, the resources in each partition are configured to provide data transfer connections capable of transferring data from one port to another in the data communications device. The connections of at least one partition are configured in parallel to the connections of at least one other partition, such that the partitions transfer data from a source to a destination in a parallel manner, and such that if one switch control mechanism fails, a connection provided by one or more routes supported by remaining switch control mechanisms will remain active to continue to transfer data.
The methods and arrangements of the invention are preferably implemented primarily by computer software and hardware mechanisms within a data communications device apparatus. As such, other embodiments of the invention include a computer program product having a computer-readable medium including computer program logic encoded thereon for transferring data through a data communications device. The computer program logic, when executed on at least one processing unit with the data communications device, causes the at least one processing unit to perform the techniques outlined above, as well as all operations discussed herein that can be performed by software program(s) executing on computer hardware. In other words, these arrangements of the invention are generally manufactured as a computer program stored on a disk or other such media that can be loaded into a computer or data communications device to make the device perform according to the operations of the invention.